package com.yxp.offer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Auther     : yxpweb
 * @Date       : 2021/5/6 9:35
 * @Description: 二叉树的构造
 */
public class MyBinarySearchTree {

    private class BinaryNode {
        BinaryNode left;
        BinaryNode right;
        int ele;

        public BinaryNode(int ele) {
            this.ele = ele;
        }
    }

    private BinaryNode root;//根节点

    //根据数组 arr 中的元素构造一棵二叉排序树
    public void buildTree(int[] arr) {
        for (int node : arr) {
            insert(node);
        }
    }

    private void insert(int ele) {
        root = insert(root, ele);
    }

    private BinaryNode insert(BinaryNode root, int ele) {
        //递归的结束条件.base condition
        if (root == null)
            return new BinaryNode(ele);

        if (root.ele > ele)
            root.left = insert(root.left, ele);
        else if (root.ele < ele)
            root.right = insert(root.right, ele);
        else
            root.left = insert(root.left, ele);

        return root;//若某结点的左右孩子不空,在后续的递归调用中该结点的左右指针是不会变的.
    }

    public void printTreeLineByLine(BinaryNode root) {
        Queue<BinaryNode> queue = new LinkedList<MyBinarySearchTree.BinaryNode>();

        int current = 1;//当前层未打印的结点个数
        int next = 0;//下一层待打印的结点个数

        queue.offer(root);
        BinaryNode currentNode;
        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            current--;
            System.out.print(currentNode.ele + " ");//打印当前节点

            if (currentNode.left != null) {
                queue.offer(currentNode.left);
                next++;
            }
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
                next++;
            }

            if (current == 0)//表示本行所有的结点已经打印完了
            {
                System.out.println();//打印下一行
                current = next;
                next = 0;
            }
        }
    }


    public void buildCompleteTree(int[] nodes) {
        Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
        root = new BinaryNode(nodes[0]);
        BinaryNode currentNode = null;

//        queue.offer(root);
        int next = 0;//标记当前结点的左右孩子是否已经构造完毕
        currentNode = root;//保存当前正在"构造"的结点
        int count = 1;//记录数组中的已经构造的元素
        while (count < nodes.length) {
            if (next == 2)//某结点的左右孩子已经构造好了
            {
                currentNode = queue.poll();
                next = 0;
            }
            if (currentNode.left == null && count < nodes.length) {
                currentNode.left = new BinaryNode(nodes[count++]);
                queue.offer(currentNode.left);
                next++;
            }
            if (currentNode.right == null && count < nodes.length) {
                currentNode.right = new BinaryNode(nodes[count++]);
                queue.offer(currentNode.right);
                next++;
            }
        }
    }


    //test
    public static void main(String[] args) {
        MyBinarySearchTree bst = new MyBinarySearchTree();
        int[] arr = {2, 4, 5, 1, 3};
//        bst.buildTree(arr);
//        bst.printTreeLineByLine(bst.root);

        System.out.println("----------------");

        bst.buildCompleteTree(arr);
        bst.printTreeLineByLine(bst.root);
    }
}